1. Field
Embodiments of the invention relate to the field of transactional memory. More particularly, embodiments of the invention relate to a hybrid hardware and software implementation of transactional memory access.
2. Description of Related Art
Transactional memory service allows applications, programs, modules, etc., and more particularly application program interfaces (APIs), to access memory in an atomic, consistent, and isolated manner. For example, transactional memory may be used as part of a run time engine for managing persistent, pointer-rich data structures, such as databases, and directory services.
An API may be thought of as a language or message format used by an application, program, module, etc., to communicate with a system program such as an operating system or a database management system (DBMS). APIs may be implemented by writing function calls in a program, which provide the linkage to a specific subroutine for execution. Thus, an API implies that some program module or routine is either already in place, or is linked to, in order to perform tasks requested by a function call.
Transactional memory makes it easier to write parallel programs and the use of transactional memory allows for different threads to proceed simultaneously thereby gaining extremely high processing efficiencies. However, currently the programmer has to make a difficult choice in utilizing transactional memory.
One choice is to use a hardware-only implementation of a transactional memory application program interface (API) where the programmer is responsible to keep track of a program's hardware resource requirements and ensure that they do not exceed the hardware resources available. The applicability and usability of transactional memory (hereinafter TM) is limited under this approach. The alternative is to use a software-only implementation of TM API that is easy to program (because there is practically no resource limit) but the software approach suffers from high execution time overheads.
Looking more particularly at transactional memory (TM), TM is derived from database transactions. In databases, a transaction is a group of operations that must satisfy four properties referred to as the ACID properties. The first ACID property is atomicity. Atomicity requires that a database transaction is performed in an all-or-nothing manner. The transaction may be aborted either because the program aborts or due to an error. Atomicity requires that either all of the operations of the transaction are performed or none of them are performed. The second ACID property is consistency. Consistency requires that if the database is in a consistent state before the transaction is performed, the database should be left in a consistent state. The third ACID property is isolation. The isolation property states that all transactions to be performed have to appear to be done in some sort of serial order (i.e., they should be serializable). The last and fourth property required to be under ACID is durability. Durability requires a transaction to survive a machine crash. That is, a transaction has to be written to a stable storage device (e.g. disk) before it can be committed. However, it should be noted that not all implementations of TM, require a transaction to satisfy all of the four above-described properties. For example, in some implementations, durability is not a requirement.
Beyond being compliant with all or some of the above-described ACID properties, transactions and databases utilizing transactional memory are often required to support concurrent execution, deadlock freedom, and non-blocking properties. Typically, concurrent execution of non-conflicting transactions is supported by transactional memory systems. Some database implementations use locks (e.g. two phase locking) to implement these types of transactions. Consequently, deadlocks can occur in these cases. Deadlock freedom is implemented in transactional memory systems by, once detecting a deadlock, recovering from a deadlock by simply aborting some of the transactions. The non-blocking or obstruction-freedom property is required to prevent a thread from hindering the progress of other threads in transactional memory systems.
To date, there are two common approaches to implement transactional memory accesses utilizing application program interfaces (APIs): one of which is a purely hardware implementation; and the other of which is a purely software implementation. The hardware implementation is based on a multi-processor architecture as set forth in Transactional Memory: Architectural Support for Lock-Free Data Structures (Maurice Herlihy, J. Eliot B. Moss: Transactional Memory: Architectural Support for Lock-Free Data Structures, International Society for Computers and Their Application, (ISCA) 1993: 289-300). This approach will be hereinafter referred to as the Pure Hardware Approach.
The Pure Hardware Approach provides an efficient and easy-to-use lock-free synchronization method. The Pure Hardware Approach avoids many of the subtle correctness problems associated with parallel programming in addition to guaranteeing freedom from priority-inversion, convoying, and deadlocks typically associated with lock-based synchronization methods.
Unfortunately, the Pure Hardware Approach requires careful resource management by the programmer. As such, the Pure Hardware Approach is very difficult to implement with a wide variety of more advanced processor structures. Typically, software is required to be portable across processor implementation and such careful tuning of resources at the application level limits the use of the pure hardware approach. Furthermore, in operation, the Pure Hardware Approach only utilizes transaction cache in transactional memory, and because of this limited resource, process threads are not guaranteed to complete resulting in program malfunctions.
Another common approach of utilizing transactional memory accesses with APIs is by utilizing a purely software approach, for example, as set forth in Software Transactional Memory for Dynamic-Sized Data Structures (Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, Software Transactional Memory for Dynamic-Sized Data Structures, Principles of Distributed Computing (PODC) 2003.) This approach will be hereinafter called The Pure Software Approach. The power of the Pure Software Approach is that the programmer may be completely oblivious of the specific techniques employed to provide transactional memory semantics and the API is particularly easy to program. Unfortunately, in operation, the Pure Software Approach technique results in significant slow-downs caused by software overheads.